package com.example.leetcode.prcatice;

/**
 * 剑指 Offer 10- I. 斐波那契数列 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 *
 * <p>F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 */
public class Offer10_1 {

    public int fib(int n) {

        if (n == 0){
            return 0;
        }
        if (n == 1 ){
            return 1;
        }
        int[] sum = new int[n+1];
        sum[0] = 0;
        sum[1] = 1;
        int t = 1000000007;
        for (int i = 2;i<=n;i++){
            sum[i] = (sum[i-1] + sum[i-2]) % t;
        }
        return sum[n];
    }
}


class TestOffer_I{
  public static void main(String[] args) {
    int n = 5;
    Offer10_1 o = new Offer10_1();
    System.out.println(o.fib(n));
  }
}